1. Field of the Invention
This invention relates to the field of video processing and in particular to the interpolation of pixels within a video processing system.
2. Background Art
The use of pixel interpolation is well known in the field of video processing because in this field a great deal of pixel data must be stored, encoded, transmitted, decoded, scaled and shifted. So much pixel data is operated upon in video processing that even storing and retrieving the data are difficult. For example, D. L. Sprague, N. J. Fedele and L. D. Ryan in a U.S. patent application Ser. No. 918,275, filed 14 Oct. 1986, entitled "Non-Dedicated Image Memory Using Separate Bit-Nap Organizations For Luminance and Chrominance Variables", describe a system for retrieving stored images in digital form from video random-access memory (VRAM).
The VRAM taught in Sprague et al. is a dual-ported memory including a dynamic random-access memory with a random-access read/write port. It also includes a relatively small, auxiliary, static, serial memory with a serial output port. The storage locations of the auxiliary memory may be loaded with pixel information in parallel from any row of storage locations in the larger dynamic memory upon command. Thereafter the auxiliary memory has its storage locations scanned by a counter operating as an address generator and it is read out in a shift register operation to supply a stream of video data.
In the system of Sprague et al., the pixels to be interpreted are described in terms of luminance and chrominance components. Each of the components has its own bit-map organization associated therewith in the dynamic memory portion of VRAM. Groups of bits descriptive of the luminance or chrominance of a pixel are stored together in a conformal mapping of the display in a bit-map-organized memory. The luminance components are generally more densely sampled in image field space than the chrominance components are. This is done to conserve image memory, recognizing that visual acuity for chrominance is less than that for luminance.
The VRAM is linearly packed. This means that the raster scanning of pixel codes is stored in successive rows of the dynamic memory. Rows in dynamic memory do not necessarily have a 1:1 correspondence with scan lines in the ultimate display. A formatter known as a "pixel unwrapper" takes a stream of data supplied to it from the VRAM serial output port and passes it into scan lines of successive pixel codes.
During line trace intervals in the display, VRAM supplies data from its output port. From this data the pixel-unwrapper generates a stream of pixel codes describing luminance in real time. During selected line retrace intervals in the display, VRAM supplies data from its serial output port from which data the pixel unwrapper generates two streams of pixel codes describing chrominance in a compressed-in-time and advanced-in-time format.
Each stream of chrominance components may be supplied to a respective chrominance re-sampling apparatus. Each re-sampling apparatus may comprise a respective odd-line line-storage memory, a respective even-line line-storage memory and a pixel interpolator.
Successive lines of each stream of compressed chrominance data are selected on an alternating basis for writing into its odd-line or its even-line line-storage memory. These line storage memories act as a rate-buffer to supply samples to their interpolator. The interpolator generates samples of the chrominance component with compression removed and with delay to temporally align them with the real-time luminance samples.
The luminance samples and two sets of chrominance samples are converted from digital to analog form and are linearly combined, for generating red, green and blue analog video signals. These analog video signals are amplified and gamma-corrected to provide drive signals for the display apparatus, typically a color kinescope.
The Sprague, Fedele and Ryan interpolator uses a cascade of n basic interpolator blocks and a multiplexer to re-sample each set of supplied chrominance samples 2.sup.n times more densely in both the direction of pixel scan and direction of line advance. Each basic interpolator block includes three multiplexers, three adders, two clocked unit-delay latches and bit place shift circuitry. The teaching of this device is directed to interpolator circuitry for expanding video data that can be more readily programmed to do either 2:1 or 4:1 spatial interpolation and that reduces the amount of hardware associated with spatial interpolation. However, these operations may be very computationally intensive. Therefore it is desirable to perform interpolation, such as the interpolation taught by Sprague, Fedels and Ryan, using less time and/or less hardware circuitry.
It is known in the prior art that reduction of the complexity of the interpolation problem may be achieved by manipulating the interpolation equations. The simplest form of interpolation to attempt to reduce is in the field of one-dimensional interpolation. One-dimensional interpolation involves the weighted summation of two values, for example, as expressed by the equation: EQU I=xA+(1-x) B. Equation (1)
In this equation A and B are the two input values to be interpolated and x is the fractional weight term. The solution of this equation requires two add/subtract operations and two multiplications.
It is known to rearrange this equation to reduce it to the following form: EQU I=x(A-B)+B. Equation (2)
When the basic one-dimensional interpolation equation is rearranged into this form, the solution of the interpolation requires one subtraction, one addition, and one multiplication. Thus, this rearranged form requires one less multiplication. Because this rearranged form requires fewer mathematical operations, it is advantageous to design a circuit to solve the equation in this rearranged form. This advantage can be realized in the form of decreased space requirements on the semiconductor chip or in performing the interpolation more quickly using the same amount of space. However, it is desirable to further reduce the amount of space or time required to perform the interpolation.
U.S. Pat. No. 5,148,381, entitled "One-Dimensional Interpolation Circuit and Method Based on Modification of a Parallel Multiplier", filed Feb. 7, 1991, by Sprague teaches further reduction. The method of sprague starts by assuming that the fractional weight term of the interpolation, x, is a four bit unsigned binary number. Equation (1) may be scaled by sixteen to give: ##EQU1## where: EQU y =16x
and y is a four bit unsigned integer with values from zero to fifteen which may be the interpolation weight term.
Because interpolation weight term y was a four bit positive integer, EQU 16-y=.alpha.y+1, Equation (4)
where .alpha.y is the one's complement of y wherein each bit of y is complemented. Substituting Equation (4) into the right hand side of Equation (3) provides: EQU 16I=yA+.alpha.yB+B. Equation (5)
A circuit suitable for the implementation of Equation (5), was provided by a modified multiplier array wherein things were substituted.
An implementation of an interpolator based on Equation (5) is generally more hardware efficient than prior art implementations based on either Equation (1) or Equation (2). The implementation based on Equation (5) needs one less subtractions compared with the implementation of Equation (2) because the implementation of Equation (5) does not require the generation of the (A-B) term required by the implementation of Equation (2).
The reason for the increase in efficiency provided by Equation (5) is that adders forming a multiplier in an implementation based on Equation (2) are not fully utilized when one or more bits of weight term y are equal to zero. In the case where one or more bits of y are equal to zero, the row of adders that corresponds to a zero bit of y simply passes the partial product on to the next stage. In the implementation of the present invention based on Equation (5), each stage of adders adds either an A term or a B term of the partial product. It will be understood by those skilled in the art that Equation (5) can be implemented by hardware or software.
Even though this method performs interpolations much more efficiently, it only interpolates in one dimension and in some applications it is advantageous to interpolate in more than one dimension. For example, it is known to perform interpolations in two and three dimensions. An example of the two-dimensional interpolation is multimedia applications. In these applications scaling may be used to allow a still or a motion video image to be displayed in an arbitrarily sized window covering a portion of the display device. Many methods for multi-dimensional interpolation are known. For example, it is known to perform such multi-dimensional interpolation as a series of one-dimensional interpolations.
Referring now to FIG. 1, there is shown prior art two-dimensional bilinear pixel interpolation method 1. It is known to perform two-dimensional bilinear interpolation pixel method 1 upon four input pixels 2a-d with two interpolation weights, a horizontal interpolation weight w.sub.x and a vertical interpolation weight w.sub.y. In bilinear pixel interpolation method 1, input pixels 2a-d are positioned horizontally and vertically adjacent with respect to each other and pixel 2f is a value between pixels 2a-d which is determined by the interpolation process.
The value of pixel 2f between pixels 2a-d may be calculated, for example, by a sequence of conventional one-dimensional interpolation. The interpolation of pixel 2a and pixel 2c to determine pixel 2e may be performed along dotted line 4 according to vertical interpolation weight w.sub.y. The interpolation of pixel 2b and pixel 2d to form pixel 2g may be performed along dotted line 8, also according to vertical interpolation weight w.sub.y. The interpolation of pixel 2e and pixel 2g to determine pixel 2f may then be performed along dotted line 6 according to horizontal interpolation weight w.sub.x.
The bilinear interpolation operation of method may be performed as three one-dimensional interpolations: (1) pixel 2e=(pixel 2a, pixel 2c), (2) pixel 2g=(pixel 2b, pixel 2d), and (3) pixel 2f=(pixel 2e, pixel 2g). In this formulation (pixel m, pixel n) represents a conventional one-dimensional linear interpolation between pixel m and pixel n, for example, as set forth in Equation (5). In some applications which are sequentially repeated, it is possible that only two interpolations rather than three may be performed in order to practice bilinear pixel interpolation method 1. The result of one of the one-dimensional interpolations, for example pixel 2g=(pixel 2b, pixel 2d), may be remembered from the previous two-dimensional interpolation operation.